package 二分.二分答案;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/19 17:37
 */
public class leetcode6325修车的最少时间 {

    /*
      思想有点类似于 ** 左程云的画家画画** 问题
      还是要建立一个 二分答案的 敏感性！  （猜想一下， 答案可能会在 哪个区间里面）
      ==
      非常核心的 一个点,好像是, 所有的员工是同时工作的!
      这好像是一个非常核心的点!

     */

    /*
    答案的范围 ： [1, 10 ^ 14]
    最快时间: 只有一 辆车要修, && max(rank[i]) = 1 ,此时时间就是 1
    最大时间: 只有一个员工 && rank[0] = 100 && 要修的车为 10 ^ 6 , 此时时间就是 10 ^ 14
    ==
    还一个要注意的点,就是 所有的员工一起工作, 所以最终的时间 , 就是 花费时间最多的那名员工的 时间, 这个时间 也就是我们 二分答案的 这个时间  ans
    核心: 如果 所有的员工 都按照 ans 时间, 那么所有的员工的 修车的总和, 一定会 >= 给出的 cars
    所以: 枚举 ans , 求出 所有员工 在ans 时间内修车的 总和 >= cars , 找到最小的ans
    r * n ^ 2 = ans (t)    then : n = sqrt( ans / r )
     */
    public long solution(int ranks[], int cars) {
        long l = 1, r = 100000000000000l;
        while (l < r) {
            long mid = l + r >> 1;
            int car = 0;
            for (int i = 0; i < ranks.length; i++) {
                /*
                 问：开方直接取整的做法是否会有精度误差？
                答：代码中对整数开方，只要整数转浮点没有丢失精度（在 2 ^ 53 - 1，
                开方出来的整数部分就是正确的。具体可以参考 IEEE 754。
                 */
                car += Math.sqrt(mid / ranks[i]);
            }
            if (car >= cars) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }


    /*
     这是 arignote 的一个写法！ 确实牛逼
     */
    public long repairCars(int[] ranks, int cars) {
        long left = 1, right = 100000000000000L;
        while (left < right) {
            long mid = (left + right) / 2, count = 0;
            for (int rank : ranks) {
                count += Math.sqrt(mid / rank);
            }
            if (count < cars) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }


}
